(1) Field of the Invention
The present invention relates to an authentication technique that uses a public key encryption technique, and in particular to a technique for specifying a revoked public key certificate.
(2) Description of the Related Art
Systems that use the Internet as a communication infrastructure have increased with the rapid spread of Internet usage in recent years. One example is electronic transactions for buying and selling goods via the Internet.
In such a system that uses the Internet as a communication infrastructure, it is essential to confirm that a party with which communication is performed (hereinafter referred to as an “opposite party”) is a legal participant. Such confirmation is called authentication. In the following, the term “device” is used to refer to both cases in which the opposite party is a device that is operated by a person, and the opposite party is a device that performs processing according to determined procedures. Authentication of the opposite party is called device authentication. Note that “certify” denotes showing that a device is legal, in other words that the device is a legal participant in the system, and “validate” denotes confirming the legality of the opposite party. The concept of authentication includes both certification and validation.
An encryption technique is usually used in device authentication. Specifically, the certifying party has secret data showing that it is a legal participant in the system, and certifies its legality by showing the validating party that it (the certifying party) has the secret data. On the other hand, the validating party validates the legitimacy of the certifying party by confirming that the certifying party has the secret data. In a communication path, such as the Internet, where anyone can obtain communication data, it is imperative that secret data (authentication data) used in the above-described authentication is not leaked to a third party that is not associated with the authentication. This is because if the secret data is leaked to a third party, the device that has obtained the secret data can masquerade as the original device. For this reason, authentication data is transmitted in an encrypted state, only to the verifying party.
Types of encryption techniques include a common key encryption technique and a public key encryption technique. In the common key encryption technique the key for encryption and the key for decryption have the same value. On the other hand, in the public key encryption technique the key for encryption and the key for decryption have different values.
The fact that the validating party has the same secret as the certifying party for authentication in the common key encryption technique means that there is a danger that the verifying party may masquerade as the certifying party. The so-called password method is equivalent to this technique. On the other hand, in authentication in the public key encryption technique the certifying party certifies using a public key encryption technique secret key, and the verifying party verifies using a public key that corresponds to the secret key. Since the secret key cannot be made from the public key, the verifying party is unable to masquerade as the certifying party after authentication has finished. Consequently, the public key encryption method is preferable for performing the above-described authentication.
Note that in authentication that uses the public key encryption method, “sign” denotes performing processing using the secret key, and “verify” denotes confirming legality of the signature using a public key that corresponds to the secret key.
The following is one example of opposite party authentication processing using the public key authentication technique. Specifically, a first device transmits random number data to a second device as challenge data, and the second device generates a signature text by signing the received random number data with its own secret key, and returns the signature text to the first device as response data. Lastly, the first device verifies the returned signature text using the second device's public key.
In the described authentication using the public key encryption method, it is a prerequisite that the public key be valid in the system.
For this reason, usually a “public key certificate” (“approval” to have a public key) showing that the public key is a legal public key corresponding to the device is issued by an organization, called a certificate authority, in the system. The public key certificate is data formed by concatenating an ID, a validity period, a public key, and so on, and attaching the electronic signature of the certificate authority to the concatenated data. A device that receives the public key certificate confirms that the electronic signature of the certificate authority is correct in regard to the data, and then confirms the content of the public key certificate from the ID of the opposite device, the present time, and so on, before confirming that the public key is correct.
In addition, the certificate authority issues a certificate revocation list (hereinafter referred to as a “CRL”). The CRL is a list of information that specifies revoked public key certificates, in order to notify devices of public key certificates that were issued in the past that belong to devices that are not legal and that have been removed from the system. The electronic signature of the certificate authority is attached to the CRL.
In this way, trading with an illegal opposite device can be prevented by, when authenticating an opposite device using the opposite device's public key, first obtaining the opposite device's public key certificate and confirming that the obtained public key certificate is not registered in the CRL, in other words, by confirming that the public key certificate is not revoked, before performing the above-described authentication.
Note that since the format, actualization and so on of CRLs are commonly known techniques, details are not described here. One example is disclosed in Document 1, which describes a CRL format (data structure) defined by the X. 509 standard determined by ISO/IEC/ITU.
Document 2 and Document 3 disclose methods for linearly expressing a tree structure in a tree structure data storage method that is used as one data format for storing numerous public key certificate IDs that are to be revoked. In these methods the tree structure is expressed linearly by arranging the nodes in the tree structure following particular rules. For example, a method of arranging the nodes in order of levels is described in Document 3, p. 136. According to this method, levels (that correspond to layers in the tree structure) are arranged in ascending order, and within each level the nodes are arranged from left to right.
Arranging the nodes based on specific rules enables the tree structure to be constructed in the device from the linearly arranged information.
<Document 1>
W. Ford and M. Baum, Digitaru Shomei to Ango Gijutsu (Digital Signatures and Encryption Techniques), trans. S. Yamada, Pearson Education Japan, 2001.
<Document 2>
G. Salton, Manipulation of Trees in Information Retrieval, Communication of the ACM 5, 1962.
<Document 3>
Knuth, “Kihon Sanhou/Jouhou Kouzou (Basic Algorithms/Information Structure)”, trans. Yoneda & Kakehi, Saiensu-sha, 1978.
As described above, before authenticating an opposite device using the opposite device's public key, a device obtains the CRL, stores the obtained CRL in an internal memory, confirms whether the opposite device's public key certificate ID is in the stored CRL, and when the public key certificate ID is not included, performs authentication. For this reason, it is necessary for the device to have sufficient memory capacity to store the CRL.
However, a conventional CRL includes the IDs of all revoked public key certificates, and is therefore proportional in size to the number of revoked public key certificates. Consequently, when the number of revoked public key certificates increases, the size of the CRL also increases.
For this reason, a problem arises that it is unrealistic to estimate the maximum size of the CRL and provide sufficient memory capacity in the device for storing the CRL.
For example, suppose that the total number of public key certificates in the system overall is 230 (approximately 1 billion), 0.01%, in other words 100,000, of the certificates are revoked, and the size of each ID is 30 bits. In a conventional CRL that includes all the IDs, the size of the CRL will be 30 bits*100,000=approximately 375 KB. Consequently, approximately 375 KB of memory must be provided in the device for storing the CRL. However, if 0.02% of the certificates, in other words 200,000, are revoked, the size of the CRL will be 30 bits*200,000=approximately 750 KB, and approximately 750 KB of memory must be provided in the device. If the number of revoked certificates further increases, even more memory capacity must be provided.